package Algorithms.chapter3.ch1;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class BST<Key extends Comparable<Key>,Value> {
    private Node root;
    private class Node {
        private Key key;
        private Value val;
        private Node left, right;
        private int N;

        public Node(Key key, Value val, int N) {
            this.key = key;
            this.val = val;
            this.N = N;
        }
    }

    public void show(){
        show(root);
        System.out.println();
    }

    private void show(Node x){
        if(x==null){return;}
        show(x.left);
        System.out.print(x.key);
        show(x.right);

    }

    public int size(){
        return size(root);
    }
    private int size(Node x){
        if (x==null) return 0;
        else return x.N;
    }
    public Value get(Key key){
        return get(root,key);
    }
    private Value get(Node x,Key key){
        if (x==null)return null;
        int cmp=key.compareTo(x.key);
        if(cmp<0) return get(x.left,key);
        else if(cmp>0) return get(x.right,key);
        else return x.val;
    }
    public void put(Key key,Value val){
        root = put(key,val,root);
    }
    private Node put(Key key,Value val,Node x){
        if(x==null)return new Node(key,val,1);
        int cmp=key.compareTo(x.key);
        if (cmp<0) x.left=put(key, val, x.left);
        else if (cmp>0) x.right=put(key,val,x.right);
        else x.val=val;//忘记写了
        x.N=size(x.left)+size(x.right)+1;
        return x;
    }

    //查找最小键值
    public Key min(){
        return min(root).key;
    }
    private Node min(Node x){
        if(x.left==null) return x;
        return min(x.left);
    }

    //向下取整，小于key的最大值
    public Key floor(Key key){
        Node x=floor(root,key);
        if(x==null)return null;
        return x.key;

    }
    private Node floor(Node x,Key key){
        if(x==null)return null;
        int cmp = key.compareTo(x.key);
        if (cmp==0)return x;
        if(cmp<0)return floor(x.left,key);
        Node t = floor(x.right,key);
        if(t!=null) return t;
        else return x;
    }

    //select返回排名为k的结点
    public Key select(int k){
        return select(root,k).key;
    }
    private Node select(Node x,int k){
        if (x==null) return null;
        int t = size(x.left);
        if (t>k) return select(x.left,k);
        else if (t<k) return select(x.right,k-t-1);
        else return x;
    }
    //rank
    public int rank(Key key){
        return rank(key,root);
    }
    private int rank(Key key,Node x){
        if (x==null) return -1;
        int cmp=key.compareTo(x.key);
        if (cmp<0) return rank(key,x.left);
        else if(cmp>0) return rank(key,x.right)+1+size(x.left);
        else return size(x.left);
    }

    //deleteMin
    public void deleteMin(){
        root = deleteMin(root);
    }
    private Node deleteMin(Node x){
        if (x.left==null) return x.right;
        x.left = deleteMin(x.left);
        x.N=size(x.left)+size(x.right)+1;
        return x;
    }
    //delete
    public void delete(Key key){
        root = delete(root,key);
    }
    private Node delete(Node x,Key key){
        if (x==null) return null;
        int cmp=key.compareTo(x.key);
        if(cmp<0) x.left = delete(x.left,key);
        else if(cmp>0) x.right = delete(x.right,key);
        else
        {
            if(x.right==null) return x.left;//最大或者最小的情况
            if(x.left == null) return x.right;//直接返回
            Node t = x;
            x = min(t.right);
            x.left = t.left;
            x.right = deleteMin(t.right);
        }
        x.N = size(x.left)+size(x.right)+1;
        return x;
    }

    Queue<Node> queue = new ArrayDeque<>();
    String res = new String();

    // Encodes a tree to a single string.
    public String serialize(){
        return serialize(root,"");
    }

    public String serialize(Node root,String res) {
        if(root == null) {
            res = res + "null,";
        }
        else {
            res = res + root.val + ',';
            res = serialize(root.left, res);
            res = serialize(root.right, res);
        }
        return res;

    }




}
